package org.cabbage.lintcode;

import java.util.ArrayList;
import java.util.List;

/**
 * n皇后问题是将n个皇后放置在n*n的棋盘上，皇后彼此之间不能相互攻击。
 * <p>
 * 给定一个整数n，返回所有不同的n皇后问题的解决方案。
 * <p>
 * 每个解决方案包含一个明确的n皇后放置布局，其中“Q”和“.”分别表示一个女王和一个空位置。
 *
 * @author Administrator
 */
public class SolveNQueens {

    public static void main(String[] args) {
        SolveNQueens snq = new SolveNQueens();
        List<List<String>> reslut = snq.solveNQueens(1);
        reslut.forEach(list -> {
            list.forEach(System.out::println);
            System.out.println();
        });
    }

    public List<List<String>> solveNQueens(int n) {
        if (n == 1) {
            List<String> t = new ArrayList<String>();
            t.add("Q");
            List<List<String>> t2 = new ArrayList<List<String>>();
            t2.add(t);
            return t2;
        }

        List<List<String>> result = new ArrayList<List<String>>();
        int[] map = new int[n];
        int y = 0;
        while (map[0] < n) {
            if (y == n - 1) {
                for (int i = 0; i < n; i++) {
                    if (!attack(map, y, i)) {
                        map[y] = i;
                        add(result, map);
                    }
                }
                map[y] = 0;
                map[--y]++;
            } else {
                boolean hasValue = false;
                for (int i = map[y]; i < n; i++) {
                    if (!attack(map, y, i)) {
                        map[y] = i;
                        hasValue = true;
                        break;
                    }
                }
                if (hasValue) {
                    y++;
                } else {
                    map[y] = 0;
                    map[--y]++;
                }
            }
        }
        return result;
    }

    private boolean attack(int[] map, int y, int x) {
        for (int i = 0; i < y; i++) {
            if (Math.abs(i - y) == Math.abs(map[i] - x) || map[i] == x) return true;
        }
        return false;
    }

    private void add(List<List<String>> result, int[] map) {
        List<String> temp = new ArrayList<String>();
        for (int i : map) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < map.length; j++) {
                if (j == i) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            temp.add(sb.toString());
        }
        result.add(temp);
    }

}
